//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 
//
// 测试用例的答案是一个 32-位 整数。 
//
// 子数组 是数组的连续子序列。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 2 * 10⁴ 
// -10 <= nums[i] <= 10 
// nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数 
// 
// Related Topics 数组 动态规划 👍 1532 👎 0

package leetcode.editor.cn;

public class _152_MaximumProductSubarray {
    public static void main(String[] args) {
        Solution solution = new _152_MaximumProductSubarray().new Solution();
        int[] nums = new int[] {2,3,-2,4};
//        int[] nums = new int[] {-2,0,-1};
        System.out.println(solution.maxProduct(nums));
    }

    class Solution {
        public int maxProduct(int[] nums) {
            int max = nums[0];
            int min = nums[0];
            int res = nums[0];
            for (int i = 1; i < nums.length; i++) {
                max = Math.max(nums[i], Math.max(nums[i] * max, nums[i] * min));
                min = Math.min(nums[i], Math.min(nums[i] * max, nums[i] * min));
                res = Math.max(res, max);
            }
            return res;
        }
    }

    // 官方解法，动态规划，同时大小动态，类似求和，多了个正负号
    class Solution2 {
        public int maxProduct(int[] nums) {
            int[] maxF = new int[nums.length];
            int[] minF = new int[nums.length];

            System.arraycopy(nums, 0, maxF, 0, nums.length);
            System.arraycopy(nums, 0, minF, 0, nums.length);

            for (int i = 1; i < nums.length; i++) {
                maxF[i] = Math.max(nums[i], Math.max(nums[i] * maxF[i - 1], nums[i] * minF[i - 1]));
                minF[i] = Math.min(nums[i], Math.min(nums[i] * maxF[i - 1], nums[i] * minF[i - 1]));
            }

            int res = maxF[0];
            for (int num : maxF) {
                res = Math.max(res, num);
            }

            return res;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 不仅超时，还有错误，万一没1大就凉凉
    class Solution1 {
        public int maxProduct(int[] nums) {
            int res = Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                for (int j = i; j < nums.length; j++) {
                    int ji = 1;
                    for (int k = i; k < j; k++) {
                        ji *= nums[k];
                    }
                    res = Math.max(ji, res);
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}